package libnetdb.dm.assoc.dhp;
import java.util.*;

import libnetdb.dm.assoc.base.*;
import libnetdb.dm.assoc.util.*;


class HashTable implements SearchStructure{

    private int leaf_lmt, fanout;

    private class HashNode{
        private boolean split_flag = true;
        private int sid = -1;
        private HashNode subnode[] = null;
        private Collection set = new ArrayList();

        public HashNode(){}

        private int hash(int a){
            return Math.abs(a*0x743EA79F)%subnode.length;
        }

        private int binarySearch(int ids[], int start, int end, int target){
            for(int x=(start+end)/2;start<end;x=(start+end)/2)
                if(target > ids[x]) start = x + 1;
            else end = x;
            return ids[end]==target? start:-1;
        }

        private boolean isSubset(int ids[], Itemset itemset){
            int start = 0, end = ids.length-1;
            for(int i=0;i<itemset.size();i++)
                if((start = binarySearch(ids, start, end, itemset.ids[i]))>=0)
                    start = start + 1;
            else return false;
            return true;
        }

        private void dispatch(int level, Litemset litemset){
            if(level<litemset.size()){
                int idx = hash(litemset.ids[level]);
                if(subnode[idx]==null) subnode[idx] = new HashNode();
                subnode[idx].add(level+1, litemset);
                }else set.add(litemset);
        }

        public void add(int level, Litemset litemset){
            if(subnode==null){
                if(litemset.size()>level) split_flag = true;
                set.add(litemset);
                }else dispatch(level, litemset);
            if(set.size()>leaf_lmt && split_flag){
                if(subnode==null) subnode = new HashNode[fanout];
                Collection ori_set = set;
                set = new ArrayList();
                for(Iterator it = ori_set.iterator(); it.hasNext();)
                    dispatch(level, (Litemset) it.next());
                split_flag = false;
            }
        }

        public void update(int tid, int ids[], int start){
            if(this.sid == tid) return;
            this.sid = tid;
            for(Iterator it = set.iterator(); it.hasNext(); ){
                Litemset litemset = (Litemset) it.next();
                if(isSubset(ids, litemset)) litemset.count ++;
            }
            if(subnode!=null)
                for(int i = start; i<ids.length; i++){
            HashNode node = subnode[hash(ids[i])];
            if(node!=null) node.update(tid, ids, i+1);
                }
        }
    }

    private HashNode root = new HashNode();

    public HashTable(int leaf_limit, int fanout) {
        this.leaf_lmt = leaf_limit;
        this.fanout = fanout;
    }

    public void addCandidate(Litemset candidate) {
        root.add(0, candidate);
    }

    public void update(int tid, int ids[]){
        root.update(tid, ids, 0);
    }

    public void congeal(){//Do nothing in this version
    }
}